package com.example.leetcode.math.common;

import com.example.leetcode.math.common.strategy.CustomFunction;
import com.example.leetcode.string.common.StringUtils;
import javafx.util.Pair;

import java.util.*;
import java.util.stream.Collectors;

public class MathUtils {
    public static int countEven(int num) {
        int result = 0;
        for (int i = 1; i <= num; i++) {
            if (check(i)) {
                result++;
            }
        }
        return result;
    }

    private static boolean check(int num) {
        int bitSum = 0;
        while (num > 0) {
            bitSum += num % 10;
            num /= 10;
        }
        return bitSum % 2 == 0;
    }

    public static int addDigits(int num) {
        while (num >= 10) {
            num = dealNum(num);
        }
        return num;
    }

    private static int dealNum(int num) {
        int result = 0;
        while (num > 0) {
            result += num % 10;
            num /= 10;
        }
        return result;
    }

    public static String addStrings(String num1, String num2) {
        char[] arr1 = num1.toCharArray();
        StringUtils.reverseCharArray(arr1);
        char[] arr2 = num2.toCharArray();
        StringUtils.reverseCharArray(arr2);
        int n = Math.max(num1.length(), num2.length());
        int[] result = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int sum = result[i];
            if (i < arr1.length) {
                sum += Integer.parseInt(String.valueOf(arr1[i]));
            }
            if (i < arr2.length) {
                sum += Integer.parseInt(String.valueOf(arr2[i]));
            }
            result[i] = sum % 10;
            result[i + 1] = sum / 10;
        }
        StringBuilder ans = new StringBuilder();
        if (result[result.length - 1] != 0) {
            ans.append(result[result.length - 1]);
        }
        for (int i = result.length - 2; i >= 0; i--) {
            ans.append(result[i]);
        }
        return ans.toString();
    }

    public static String convertToTitle(int columnNumber) {
        StringBuilder result = new StringBuilder();
        while (columnNumber > 0) {
            int mod = --columnNumber % 26;
            int num = mod + 65;
            char c = (char) num;
            result.insert(0, c);
            columnNumber = columnNumber / 26;
        }
        return result.toString();
    }

    public static int titleToNumber(String columnTitle) {
        if (columnTitle == null || columnTitle.length() == 0) {
            return 0;
        }
        int result = 0;
        for (int i = 0; i < columnTitle.length(); i++) {
            int num = columnTitle.charAt(i) - 65 + 1;
            result = result * 26 + num;
        }
        return result;
    }

    public static boolean isHappy(int n) {
        if (n <= 0) {
            return false;
        }
        Set<Integer> set = new HashSet<>();
        set.add(n);
        int num = 0;
        while (true) {
            while (n > 0) {
                int bit = n % 10;
                num = num + bit * bit;
                n = n / 10;
            }
            if (num == 1) {
                return true;
            }
            if (set.contains(num)) {
                return false;
            } else {
                set.add(num);
            }
            n = num;
            num = 0;
        }
    }

    public static boolean digitCount(String num) {
        int[] map = new int[10];
        int[] intnum = new int[num.length()];
        for (int i = 0; i < num.length(); i++) {
            intnum[i] = Integer.parseInt(String.valueOf(num.charAt(i)));
            map[intnum[i]]++;
        }
        for (int i = 0; i < num.length(); i++) {
            if (map[i] != intnum[i]) {
                return false;
            }
        }
        return true;
    }

    public static boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        int[] nums = {2, 3, 5};
        int index = 0;
        while (true) {
            if (index > 2) {
                return false;
            }
            if (n / nums[index] == 0) {
                return true;
            } else {
                if (n % nums[index] == 0) {
                    n = n / nums[index];
                } else {
                    index++;
                }
            }
        }
    }

    public static boolean isPowerOfThree(int n) {
        if (n <= 0) {
            return false;
        }
        int m = 1;
        while (m <= n && m > 0) {
            if (m == n) {
                return true;
            } else {
                m = m * 3;
            }
        }
        return false;
    }

    public static boolean isPowerOfFour(int n) {

        if (n <= 0) {
            return false;
        }
        int m = 1;
        while (m <= n && m > 0) {
            if (m == n) {
                return true;
            } else {
                m = m * 4;
            }
        }
        return false;

    }

    public static List<String> fizzBuzz(int n) {
        List<String> answer = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            String s;
            if (i % 3 == 0 && i % 5 == 0) {
                s = "FizzBuzz";
            } else if (i % 3 == 0) {
                s = "Fizz";
            } else if (i % 5 == 0) {
                s = "Buzz";
            } else {
                s = String.valueOf(i);
            }
            answer.add(s);
        }
        return answer;
    }

    public static boolean checkPerfectNumber(int num) {
        int sum = 0;
        for (int i = 1; i <= num / 2; i++) {
            if (num % i == 0) {
                sum += i;
            }
        }
        return sum == num;
    }

    public static int fib(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[] result = new int[n + 1];
        result[0] = 0;
        result[1] = 1;
        for (int i = 2; i < result.length; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result[n];
    }

    public static int maximumProduct(int[] nums) {
        int n = nums.length;
        if (n == 3) {
            return nums[0] * nums[1] * nums[2];
        }
        Arrays.sort(nums);
        int pcount = 0;
        for (int i = 0; i < 3; i++) {
            if (nums[n - 1 - i] > 0) {
                pcount++;
            }
        }
        if (pcount == 0) {
            return nums[n - 1] * nums[n - 2] * nums[n - 3];
        }
        if (pcount == 1 || pcount == 2) {
            return nums[n - 1] * nums[0] * nums[1];
        }
        return Math.max(nums[n - 1] * nums[n - 2] * nums[n - 3], nums[n - 1] * nums[0] * nums[1]);
    }

    public static boolean hasGroupsSizeX(int[] deck) {
        if (deck.length <= 1) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int j : deck) {
            map.merge(j, 1, Integer::sum);
        }
        List<Integer> list = new ArrayList<>();
        for (Integer num : map.keySet()) {
            list.add(map.get(num));
        }
        List<Integer> newList = list.stream().distinct().collect(Collectors.toList());
        if (newList.size() == 1) {
            return true;
        }
        Integer gcd = getListGCD(newList);
        return gcd != null && gcd >= 2;
    }

    /**
     * 求list中所有元素的最大公约数
     *
     * @param list
     * @return
     */
    private static Integer getListGCD(List<Integer> list) {
        if (list.size() == 0) {
            return null;
        }
        if (list.size() == 1) {
            return list.get(0);
        }
        Integer gcd = getGCD(list.get(0), list.get(1));
        if (gcd == null) {
            return null;
        }
        for (int i = 2; i < list.size(); i++) {
            gcd = getGCD(gcd, list.get(i));
            if (gcd == null) {
                return null;
            }
        }
        return gcd;
    }

    /**
     * 求两个数的最大公约数
     *
     * @param m
     * @param n
     * @return
     */
    private static Integer getGCD(Integer m, Integer n) {
        if (m == null || n == null) {
            return null;
        }
        int z;
        while (m % n != 0) {
            z = m % n;
            m = n;
            n = z;
        }
        return n;
    }

    public static int alternateDigitSum(int n) {
        int result = 0;
        boolean flag = true;
        List<Integer> list = new ArrayList<>();
        while (n > 0) {
            int digit = n % 10;
            list.add(digit);
            n /= 10;
        }
        Collections.reverse(list);
        for (Integer num : list) {
            if (flag) {
                result += num;
            } else {
                result -= num;
            }
            flag = !flag;
        }
        return result;
    }

    public static int[] countPoints(int[][] points, int[][] queries) {
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            for (int[] point : points) {
                double dis = Math.sqrt(Math.pow(point[0] - queries[i][0], 2) + Math.pow(point[1] - queries[i][1], 2));
                if (dis <= queries[i][2]) {
                    result[i]++;
                }
            }
        }
        return result;
    }

    public static int countPrimes(int n) {
        int[] isPrime = new int[n];
        Arrays.fill(isPrime, 1);
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] == 1) {
                ans += 1;
                if ((long) i * i < n) {
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }

    public static List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> res = new ArrayList<>();
        for (int x = 1; x <= 1000; x++) {
            for (int y = 1; y <= 1000; y++) {
                if (customfunction.f(x, y) == z) {
                    List<Integer> pair = new ArrayList<>();
                    pair.add(x);
                    pair.add(y);
                    res.add(pair);
                }
            }
        }
        return res;
    }

    public static int smallestEvenMultiple(int n) {
        if ((n & 1) == 1) {
            return n << 1;
        } else {
            return n;
        }
    }

    public static int findDelayedArrivalTime(int arrivalTime, int delayedTime) {
        return (arrivalTime + delayedTime) % 24;
    }

    public static int sumOfMultiples(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                sum += i;
            }
        }
        return sum;
    }

    /**
     * 超时
     *
     * @param nums
     * @param k
     * @param x
     * @return
     */
    public static int[] getSubarrayBeauty(int[] nums, int k, int x) {
        PriorityQueue<Pair<Integer, Integer>> queue = new PriorityQueue<>(Comparator.comparingInt(Pair::getKey));
        List<Pair<Integer, Integer>> prefix = new ArrayList<>();
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Arrays.fill(ans, 0);
        for (int i = 0; i < k - 1; i++) {
            queue.add(new Pair<>(nums[i], i));
        }
        int count = 0;
        for (int i = k - 1; i < n; i++) {
            queue.add(new Pair<>(nums[i], i));
            while (count < x) {
                Pair<Integer, Integer> poll = queue.poll();
                if (poll.getValue() < i - k + 1) {
                    continue;
                }
                prefix.add(poll);
                count++;
            }
            Integer key = prefix.get(x - 1).getKey();
            if (key < 0) {
                ans[i - k + 1] = key;
            }
            queue.addAll(prefix);
            prefix.clear();
            count = 0;
        }
        return ans;
    }

    /**
     * 使用map记录子数组窗口中每个数字出现的次数
     *
     * @param nums
     * @param k
     * @param x
     * @return
     */
    public static int[] getSubarrayBeauty1(int[] nums, int k, int x) {
        int n = nums.length;
        int[] map = new int[101];
        for (int i = 0; i < k - 1; i++) {
            map[nums[i] + 50]++;
        }
        int[] ans = new int[n - k + 1];
        for (int i = k - 1; i < n; i++) {
            map[nums[i] + 50]++;
            int count = 0;
            for (int j = 0; j < map.length; j++) {
                count += map[j];
                if (count >= x) {
                    if (j - 50 < 0) {
                        ans[i - k + 1] = j - 50;
                    }
                    break;
                }
            }
            map[nums[i - k + 1] + 50]--;
        }
        return ans;
    }

    public static int myAtoi(String s) {
        s = s.trim();
        char[] str = s.toCharArray();
        int ans = 0;
        if (s.length() == 0) {
            return ans;
        }
        int sign = 1;
        if (str[0] == '-') {
            sign = -1;
        }
        for (int i = 0; i < str.length; i++) {
            if (i == 0 && (str[i] == '-' || str[i] == '+')) {
                continue;
            }
            if (!isNumber(str[i])) {
                break;
            }
            if (sign == 1 && checkOutMaxInteger(ans, str[i])) {
                return Integer.MAX_VALUE;
            }
            if (sign == -1 && checkOutMinInteger(ans, str[i])) {
                return Integer.MIN_VALUE;
            }
            ans = ans * 10 + sign * (str[i] - '0');
        }
        return ans;
    }

    private static boolean checkOutMinInteger(int ans, char str) {
        return ans < Integer.MIN_VALUE / 10 || ((ans == Integer.MIN_VALUE / 10) && ((str - '0') > -(Integer.MIN_VALUE % 10)));
    }

    private static boolean checkOutMaxInteger(int ans, char str) {
        return ans > Integer.MAX_VALUE / 10 || ((ans == Integer.MAX_VALUE / 10) && (str - '0') > Integer.MAX_VALUE % 10);
    }

    private static boolean isNumber(char c) {
        return c >= '0' && c <= '9';
    }

    private static boolean isAlphabet(char str) {
        return (str >= 'a' && str <= 'z') || (str >= 'A' && str <= 'Z');
    }

    public static boolean confusingNumber(int n) {
        Set<Character> set = new HashSet<>();
        set.add('2');
        set.add('3');
        set.add('4');
        set.add('5');
        set.add('7');
        Map<Character, Character> map = new HashMap<Character, Character>() {{
            put('0', '0');
            put('1', '1');
            put('6', '9');
            put('8', '8');
            put('9', '6');
        }};
        StringBuilder rotate = new StringBuilder();
        char[] array = String.valueOf(n).toCharArray();
        for (char c : array) {
            if (set.contains(c)) {
                return false;
            }
            rotate.insert(0, map.get(c));
        }
        return Integer.parseInt(rotate.toString()) != n;
    }

    /**
     * 尽可能不靠近中点，步数最多
     * 尽可能一步移动到中间位置的两侧，步数最少
     *
     * @param a
     * @param b
     * @param c
     * @return
     */
    public static int[] numMovesStones(int a, int b, int c) {
        int[] nums = {a, b, c};
        Arrays.sort(nums);
        // 每次往中间移动一格是最慢的，步数最多的
        int max = nums[2] - nums[0] - 2;
        int min;
        if (nums[1] - nums[0] == 1 && nums[2] - nums[1] == 1) {
            // 三个点正好挨在一起，无需移动
            min = 0;
        } else if (nums[1] - nums[0] == 1 || nums[2] - nums[1] == 1) {
            // 存在两个点挨在一起，只需要移动一侧的点
            min = 1;
        } else if (nums[1] - nums[0] == 2 || nums[2] - nums[1] == 2) {
            // 存在两个点间隔为1，只需要移动一侧的点
            min = 1;
        } else {
            // 将两侧的点移动到中间点的两侧
            min = 2;
        }
        return new int[]{min, max};
    }

    public static List<Integer> powerfulIntegers(int x, int y, int bound) {
        int i = 0;
        Set<Integer> ans = new HashSet<>();
        while (true) {
            int curNum;
            if (x > 1) {
                curNum = (int) Math.pow(x, i);
            } else {
                curNum = 1;
            }
            if (curNum >= bound) {
                break;
            }
            int j = 0;
            int temp = curNum;
            while (true) {
                if (y > 1) {
                    curNum = (int) (temp + Math.pow(y, j));
                } else {
                    curNum = temp + 1;
                }
                if (curNum > bound) {
                    break;
                }
                ans.add(curNum);
                if (y > 1) {
                    j++;
                } else {
                    break;
                }
            }
            if (x > 1) {
                i++;
            } else {
                break;
            }
        }
        return new ArrayList<>(ans);
    }

    public static int divide(int dividend, int divisor) {
        // 处理特殊溢出情况
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        // 转为 long 类型并取绝对值
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);

        boolean negative = (dividend ^ divisor) < 0;

        int result = 0;
        System.out.println("开始快速除法计算（正数版本）");
        System.out.printf("a = %d, b = %d\n", a, b);

        while (a >= b) {
            long temp = b;
            int multiple = 1;

            System.out.println("\n开始新一轮减法：");
            while (a >= (temp << 1)) {
                System.out.printf("倍增中：temp = %d, multiple = %d\n", temp, multiple);
                temp <<= 1;
                multiple <<= 1;
            }

            System.out.printf("选择：减去 temp = %d, 加 multiple = %d\n", temp, multiple);
            a -= temp;
            result += multiple;

            System.out.printf("剩余 dividend = %d, 当前结果 = %d\n", a, result);
        }

        return negative ? -result : result;
    }

    public static double myPow(double x, int n) {
        long N = n; // 防止 n = Integer.MIN_VALUE 溢出
        return N >= 0 ? pow(x, N) : 1.0 / pow(x, -N);
    }

    private static double pow(double x, long n) {
        if (n == 0) return 1.0;

        double half = pow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
}
